# 这个不是题目，而是我自己的想法，二叉树绘制出来不直观，所以想画一个直观的二叉树
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


def re_order(pre, middle):
    if len(pre) == 0:
        return None
    if len(pre) == 1:
        return pre[0]
    root = pre[0]
    # 左右子树的中序遍历
    treeMIDL = middle[:middle.index(pre[0])]
    treeMIDR = middle[middle.index(pre[0]) + 1:]
    # 左右子树的前序遍历
    treePreL = pre[1:middle.index(pre[0]) + 1]
    treePreR = pre[middle.index(pre[0]) + 1:]

    root.left = re_order(treePreL, treeMIDL)
    root.right = re_order(treePreR, treeMIDR)
    return root


# 层遍历二叉树
def levelOrder(root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """

    def helper(node, level):
        if not node:
            return
        else:
            sol[level - 1].append(node)
            if len(sol) == level:  # 遍历到新层时，只有最左边的结点使得等式成立
                sol.append([])
            helper(node.left, level + 1)
            helper(node.right, level + 1)

    sol = [[]]
    helper(root, 1)
    return sol[:-1]


# 绘制这个二叉树
def draw_tree(sol):
    for i in range(len(sol)):
        my_sol = [[], []]
        for j in range(len(sol[i])):
            my_sol[0].append(sol[i][j].val)
            my_sol[1].append('  ')
            if sol[i][j].left is not None:
                my_sol[1].append('/')
            if sol[i][j].right is not None:
                my_sol[1].append('\\')
            if j == len(sol[i]) - 1:
                for num in my_sol[0]:
                    print("   ", num, end=' ')
                print('\n')
                for slash in my_sol[1]:
                    print(slash, end='  ')
        print('\n')


Node1 = TreeNode(1)
Node2 = TreeNode(2)
Node3 = TreeNode(3)
Node4 = TreeNode(4)
Node5 = TreeNode(5)
Node6 = TreeNode(6)
Node7 = TreeNode(7)
Node8 = TreeNode(8)

my_pre = [Node1, Node2, Node4, Node7, Node3, Node5, Node6, Node8]
my_mid = [Node4, Node7, Node2, Node1, Node5, Node3, Node8, Node6]

my_root = re_order(my_pre, my_mid)

sol = levelOrder(my_root)
draw_tree(sol)
